package com.desin.modle.datastruct.linkedlist;


import java.util.Scanner;

public class LRUByLinkedList<T> {

    private final static Integer DEFAULT_SIZE = 10;

    private SNode<T> headNode;

    /**
     * 链表长度
     */
    private Integer length;

    /**
     * 链表容量
     */
    private Integer size;

    public LRUByLinkedList() {
        this.headNode = new SNode<>();
        this.size = DEFAULT_SIZE;
        this.length = 0;
    }

    public LRUByLinkedList(Integer size) {
        this.headNode = new SNode<>();
        this.size = size;
        this.length = 0;
    }

    public void add(T data){
        //找数据的前一个节点，找到代表链表中有数据
        SNode preSNode = findPreSNode(data);

        if(preSNode!=null){
            deledtAfterSNode(preSNode);
            insertSNodeAtBegin(data);
        }else{
            if(length >= size){
                deleteSNodeAtEnd();
            }
            insertSNodeAtBegin(data);
        }
    }

    private void deleteSNodeAtEnd() {
        SNode temp = headNode;

        if(temp.getNext()==null){
            return;
        }

        //获取倒数第二个节点
        while (temp.getNext().getNext()!=null){
            temp = temp.getNext();
        }

        SNode temp1 = temp.getNext();

        temp.setNext(null);
        temp1 = null;
        length--;
    }

    private void insertSNodeAtBegin(T data) {
        SNode next = headNode.getNext();
        headNode.setNext(new SNode(data,next));
        length++;
    }

    private void deledtAfterSNode(SNode preSNode) {
        SNode next = preSNode.getNext();
        preSNode.setNext(next.getNext());
        next = null;
        length--;
    }

    private SNode findPreSNode(T data) {
        SNode temp = headNode;
        while (temp.getNext()!=null){
            if(temp.getNext().getE().equals(data)){
                return temp;
            }
            temp = temp.getNext();
        }
        return null;
    }

    public class SNode<T> {
        private T e;

        private SNode next;

        public SNode(T e, SNode next) {
            this.e = e;
            this.next = next;
        }

        public SNode() {
            this.next = null;
        }

        public T getE() {
            return e;
        }

        public void setE(T e) {
            this.e = e;
        }

        public SNode getNext() {
            return next;
        }

        public void setNext(SNode next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LRUByLinkedList<Integer> integerLRUByLinkedList = new LRUByLinkedList<>();
        Scanner sc = new Scanner(System.in);
        while (true){
            integerLRUByLinkedList.add(sc.nextInt());
            integerLRUByLinkedList.printAll();
        }
    }

    private void printAll() {
        SNode next = headNode.getNext();
        while (next!=null){
            System.out.print(next.getE() + ",");
            next = next.getNext();
        }
        System.out.println();
    }
}
